/*
 * @Author: liusheng
 * @Date: 2022-05-20 21:37:26
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-21 11:02:30
 * @Description: 剑指 Offer II 065. 最短的单词编码
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 065. 最短的单词编码
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

words.length == indices.length
助记字符串 s 以 '#' 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等
给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

 

示例 1：

输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
示例 2：

输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。
 

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 仅由小写字母组成
 

注意：本题与主站 820 题相同： https://leetcode-cn.com/problems/short-encoding-of-words/

通过次数7,073 提交次数11,087
 */

#include "header.h"

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> strs(words.begin(),words.end());

        //erase the sub string
        for (auto str : strs)
        {
            for (int i = 1; i < str.size(); ++i)
            {
                strs.erase(str.substr(i));
            }
        }

        int length = 0;
        //every length word plus one character #
        for (auto str : strs)
        {
            length += str.size() + 1;
        }

        return length;
    }
};

/*
Approach #2: Trie [Accepted]
Intuition

As in Approach #1, the goal is to remove words that are suffixes of another word in the list.

Algorithm

To find whether different words have the same suffix, let's put them backwards into a trie (prefix tree).
 For example, if we have "time" and "me", we will put "emit" and "em" into our trie.

After, the leaves of this trie (nodes with no children) represent words that have no suffix, and we will 
count sum(word.length + 1 for word in words).
*/
class Solution {
    class Trie
    {
        unordered_map<char,Trie *> children;
        bool isNotLeaf;

    public:
        Trie():isNotLeaf(false) {}

        void reverseInsert(const string & word)
        {
            Trie * node = this;
            for (auto iter = word.rbegin(); iter != word.rend(); ++iter)
            {
                if (!node->children.count(*iter))
                {
                    node->children[*iter] = new Trie();
                    node->isNotLeaf = true;
                }
                node = node->children[*iter];
            }
        }

        //this startWith is actually start with word but
        //not contain word
        bool startWith(const string & word)
        {
            int n = word.size();
            Trie * node = this;
            for (int i = n - 1; i >= 0; --i)
            {
                if (!node->children.count(word[i]))
                {
                    return false;
                }
                node = node->children[word[i]];
            }

            return node != nullptr && node->isNotLeaf;
        }

    }; 

    Trie * root;
public:
    Solution()
    {
        root = new Trie();
    }

    int minimumLengthEncoding(vector<string>& words) {
         for (auto word : words)
         {
             root->reverseInsert(word);
         }

        int result = 0;
        //use set to remove the duplicated word
        unordered_set<string> uniqWord;
         for (auto word : words)
         {
             if (!uniqWord.count(word) && !root->startWith(word))
             {
                 result += word.size() + 1;
             }
             uniqWord.insert(word);
         }

         return result;
    }
};




/*
not very good solution
*/
class Solution {
    class Trie
    {
        unordered_map<char,Trie *> children;
        bool isWord;

    public:
        Trie():isWord(false) {}

        bool reverseInsert(const string & word)
        {
            Trie * node = this;
            bool isNewWord = false;
            for (auto iter = word.rbegin(); iter != word.rend(); ++iter)
            {
                if (!node->children.count(*iter))
                {
                    isNewWord = true;
                    node->children[*iter] = new Trie();
                }
                node = node->children[*iter];
            }
            node->isWord = true;
            return isNewWord;
        }

    }; 

    Trie * root;
public:
    Solution()
    {
        root = new Trie();
    }

    int minimumLengthEncoding(vector<string>& words) {
         sort(words.begin(),words.end(),[](const string & a,const string & b){
             return a.size() > b.size();
         });

         int result = 0;
         for (auto word : words)
         {
             if (root->reverseInsert(word))
             {
                result += word.size() + 1;
             }
         }

         return result;
    }
};